#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: search_word.py 
@version:
@time: 2024/01/23


若想要在字母表中搜索单词，一定是需要按位搜索的，当搜索到了单词中的第一位后，
再搜索单词的第二位，直至搜索到单词的所有字母为止，代表该字母表中存在此单词，否则，
如果搜索某一位时未果，则说明不必继续向下深入，这条路径上不存在这个单词，需要及时回溯
避免造成资源浪费

在主调函数中需要遍历字母表寻找word中的第一个字母是否存在字母表中，存在说明位置，以此位置为起始点开始深入搜索。
在递归函数中，需要搜索当前位置的上下左右是否存在word中的下一个字母。
因此，在对每个起始点进行搜索时，需要传入的参数除了横纵坐标之外，还需要传入本轮所要搜索的是word中的第几个字母。

接下来开始考虑递归函数中的逻辑，传入的参数有i、j、n，对i、j所在位置的上下左右进行遍历，找word中的第n个字母。
当找到第n个字母时，沿着此位置继续向下深入，寻找第n+1个字母，若找不到第n个字母，则说明字母表中不存在这个单词，可以直接返回False。


只有找到第n个字母才会去找第n+1个字母。因此，当传入的参数n已经大于或等于word的长度时，说明word的所有位数均已经找到，字母表中存在这个单词，返回True即可。
"""


def search_word(table, word):
    def dfs(i, j, n):
        if n >= len(word):
            return True
        tmp = table[i][j]
        table[i][j] = 'None'
        for direct in directions:
            if 0 <= i + direct[0] < len_x and 0 <= j + direct[1] < len_y:
                if table[i + direct[0]][j + direct[1]] == word[n]:
                    if dfs(i + direct[0], j + direct[1], n + 1):
                        table[i][j] = tmp
                        return True
        table[i][j] = tmp
        return False

    len_x = len(table)
    len_y = len(table[0])
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    for _i in range(len(table)):
        for _j in range(len(table[0])):
            if table[_i][_j] == word[0]:
                if dfs(_i, _j, 1):
                    return True
    return False


table = [
    ["A", "B", "F", "J"],
    ["E", "F", "G", "H"],
    ["I", "O", "K", "L"],

]
word1 = "ABFJ"
word2 = "AEFG"
word3 = "OFG"
print(search_word(table, word1))
print(search_word(table, word2))
print(search_word(table, word3))
